package com.lun.medium;

import java.util.ArrayList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class UniqueBinarySearchTreesII {
    public List<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }
    
    private List<TreeNode> generateTrees(int start, int end) {
    	List<TreeNode> result = new ArrayList<>();
    	if(start > end) {
    		result.add(null);
    		return result;
    	}
    	
    	for(int i = start; i <= end; i++) {
    		List<TreeNode> leftSubTrees = generateTrees(start, i - 1);
    		List<TreeNode> rightSubTrees = generateTrees(i + 1, end);
    		
    		for(TreeNode ln : leftSubTrees) {
    			for(TreeNode rn : rightSubTrees) {
    				TreeNode node = new TreeNode(i);
    				node.left = ln;
    				node.right = rn;
    				result.add(node);
    			}
    		}
    	}
    	
    	return result;
    }
    
}
